//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 8 
// -10 <= nums[i] <= 10 
// 
//
// Related Topics 数组 回溯 👍 1347 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func permuteUnique(nums []int) [][]int {
res := [][]int{}
sort.Ints(nums)
var helper func(list []int, m map[int]bool)
helper = func(list []int, m map[int]bool) {
if len(list) == len(nums) {
res = append(res, append([]int{}, list...))
return
} else {
for i := 0; i < len(nums); i++ {
if i > 0 && nums[i-1] == nums[i] && m[i-1] == false {
continue
}
if _, ok := m[i]; !ok {
m[i] = true
list = append(list, nums[i])
helper(list, m)
list = list[:len(list)-1]
delete(m, i)
}
}
}
}
helper([]int{}, make(map[int]bool))
return res
}
//leetcode submit region end(Prohibit modification and deletion)
